﻿#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

class Solution
{
public:
    // 662. 二叉树最大宽度
    int widthOfBinaryTree(TreeNode* root)
    {
        vector<pair<TreeNode*, unsigned int>> q; // 用数组模拟队列
        q.push_back({ root, 1 });
        unsigned int ret = 0;

        while (q.size())
        {
            // 计算当前层数宽度
            pair<TreeNode*, unsigned int> x = q[0];
            pair<TreeNode*, unsigned int> y = q.back();
            ret = max(ret, y.second - x.second + 1);

            // 下一层入队列
            vector<pair<TreeNode*, unsigned int>> tmp;
            for (pair<TreeNode*, unsigned int> t : q)
            {
                if (t.first->left)
                    tmp.push_back({ t.first->left, t.second * 2 });
                if (t.first->right)
                    tmp.push_back({ t.first->right, t.second * 2 + 1 });
            }
            q = tmp;
        }
        return ret;
    }

    // 515. 在每个树行中找最大值
    vector<int> largestValues(TreeNode* root)
    {
        vector<int> ret;
        if (root == nullptr)
            return ret;
        queue<TreeNode*> q;
        q.push(root);

        while (q.size())
        {
            size_t sz = q.size();
            int tmp = INT_MIN;
            for (int i = 0; i < sz; i++)
            {
                TreeNode* t = q.front();
                q.pop();
                if (t->left)
                    q.push(t->left);
                if (t->right)
                    q.push(t->right);
                tmp = max(tmp, t->val);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

int main()
{
    TreeNode* n1 = new TreeNode(1);
    TreeNode* n3 = new TreeNode(3);
    TreeNode* n2 = new TreeNode(2);
    TreeNode* n5 = new TreeNode(5);

    n1->left = n3;
    n1->right = n2;
    n3->left = n5;

    cout << Solution().largestValues(n1)[2] << endl;

    return 0;
}